class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        '''
        https://blog.csdn.net/lisonglisonglisong/article/details/45543451
        拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）
        所有顶点的线性序列

        有向图中不能存在环， 还要考虑单个结点
        基于图的拓扑排序，可以检查环
        拓扑排序只有两种方式 DFS/BFS
        拓扑排序：针对的是有向无环图（DAG）才有拓扑排序
        conditions: 1:每个顶点出现仅仅一次
        2：若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

        它是一个 DAG 图，那么如何写出它的拓扑排序呢？这里说一种比较常用的方法：
            1）找入度为0的点
            2）从图中删除该顶点和所有以它为起点的有向边。
            3）重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止
            。后一种情况说明有向图中必然存在环。
        [[0,1],[0,3],[1,3],[1,2],[3,2],[3,4],[2,4]]
        [[1,0],[2,6],[1,7],[6,4],[7,0],[0,5]]
        '''
        graph = [[] for _ in range(numCourses)]
        visited = [0 for _ in range(numCourses)]
        # create graph    [1,0] 0--->1   结点0指向结点1, 要学1必须先学0
        for edge in prerequisites:
            graph[edge[0]].append(edge[1])
        # print(graph)
        for i in range(numCourses):
            if not self.dfs(graph, visited, i):  # 说明存在cycle环
                return False
        return True

    def dfs(self, graph, visited, i):
        # 如果第i个结点，已经masked为visited, 说明环被发现
        if visited[i] == -1:
            return False
        # 如果结点已经被visited,将不能在被访问
        if visited[i] == 1:
            return True

        # mark被访问过的结点visited
        visited[i] = -1
        # visit访问所有的邻居结点
        for j in graph[i]:
            if not self.dfs(graph, visited, j):
                return False
        # 访问过所有邻居结点之后，mark为已经访问过
        visited[i] = 1
        return True